package stu.day39_day.day41;

public class hw4 {
    public int maxProfit(int[] prices) {
        int len = prices.length;
        int[][] dp = new int[len][3];

        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        dp[0][2] = 0;
        // 0 1 2
        for (int i=1;i<len;i++){
            dp[i][0] = Math.max(dp[i-1][2],dp[i-1][0]);
            dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]-prices[i]);
            dp[i][2] = dp[i-1][1]+prices[i];

        }

        return Math.max(dp[len-1][0],dp[len-1][2]);

    }


    public int maxProfit(int[] prices, int fee) {
        int len = prices.length;
        int[][] dp = new int[len][2];

        dp[0][0]=0;
        dp[0][1]=-prices[0]-fee;

        for (int i=0;i<len;i++){
            dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]+prices[i]);
            dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]-prices[i]-fee);
        }

        return dp[len-1][0];
    }


    public int maxProfit(int k, int[] prices) {
        int len = prices.length;
        int[][][] dp = new int[len][k+1][2];

        for (int i=1;i<k+1;i++){
            dp[0][i][0] = 0;
            dp[0][i][1] = -prices[0];
        }

        for (int i=1;i<len;i++){
            for (int j=1;j<k+1;j++){
                dp[i][j][0] = Math.max(dp[i-1][j][0],dp[i-1][j][1]+prices[i]);
                dp[i][j][1] = Math.max(dp[i-1][j][1],dp[i-1][j-1][0]-prices[i]);
            }
        }

        return dp[len-1][k][0];

    }



}
